package com.example.hashtable;

import java.util.*;

/**
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出:
 * [
 * ["ate","eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 */
public class Leetcode49_GroupAnagrams {
    public static void main(String[] args) {
        String[] strs = new String[] {"eat", "tea", "tan", "ate", "nat", "bat",
                "ab", "ba", "aab", "baa", "bba"};
        List<List<String>> result = null;
//        result = groupAnagrams(strs);
        result = groupAnagrams2(strs);
//        result = groupAnagrams3(strs);


        result.forEach(x -> {
            x.forEach(y -> {
                System.out.print(y + ",");
            });
            System.out.println("\n============================");
        });

    }

    /**
     * 思路:
     * <p>
     * 1.创建一个map,以排序好的字符串为key,key相同的字符串组成的list为value
     * 2.遍历字符串数组
     * 将每个字符串按字母排序，异位词组，排序后必定相同
     * 3.判断map中是否存在了当前key的k-v值
     * 3.1存在，则将该字符串加入到对应k-v的list中
     * 3.2不存在，则向map中插入k-v
     * <p>
     * 然后在组内遍历每个字符串求字符串每个字符的和，和相同就为异位词
     *
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {//空数组判断
            return new ArrayList();
        }
        // map以排序后的字符串为key，相同key的strs放在同一个value的list里面
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = String.valueOf(chars);
            if (!map.containsKey(sortedStr)) {
                List<String> tmp = new ArrayList<>();
                tmp.add(str);
                map.put(sortedStr, tmp);
            } else {
                map.get(sortedStr).add(str);
            }
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 原理:任何一个大于 1 的自然数，都可以写成一系列素数的乘积，
     * 且这个素数序列（这里以及下面提到的序列都是指不考虑元素顺序的序列）是唯一的
     * <p>
     * 声明一个含26个素数的数组，分别代表26个小写英文字母(hashTable)
     * <p>
     * 1.遍历字符串数组
     * 将每个字符串按位在hashTable中查找到对应的素数后相乘得到key
     * 2.判断map中是否有这种k-v对
     * 2.1有，将字符串加入到v的list中
     * 2.2没有，创建k-v
     *
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams2(String[] strs) {
        if (strs == null || strs.length == 0) {//空数组判断
            return new ArrayList();
        }
        // 声明26个素数代表26个小写英文字母
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
                47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        HashMap<Long, List<String>> map = new HashMap<Long, List<String>>();
        for (int i = 0; i < strs.length; ++i) {
            long key = 1;
            for (int j = 0; j < strs[i].length(); ++j) {
                key *= prime[strs[i].charAt(j) - 'a'];
            }

            if (map.containsKey(key)) {
                map.get(key).add(strs[i]);
            } else {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(key, list);
            }
        }
        return new ArrayList(map.values());
    }

    /**
     * 声明一个26个字符的空数组，然后将字符串数组中的每个元素出现的次数和位置放到这个空数组中，
     * 然后将这个数组转成字符串形式((# + 字符出现的次数)26对)作为键放入map中，
     * 当再次遇到次数和位置都想同的元素，则证明是异构词，就将词加入list，最后输出map的值即可。
     */
    public static List<List<String>> groupAnagrams3(String[] strs) {
        if (strs == null || strs.length == 0) {//空数组判断
            return new ArrayList();
        }

        Map<String, List<String>> map = new HashMap<>();
        int count[] = new int[26];
        for (String s : strs) {
            // 用0填充这个数组
            Arrays.fill(count, 0);
            char ch[] = s.toCharArray();
            // 将26个小写字符出现的次数写到对应的下标中
            for (char c : ch) {
                count[c - 'a']++;
            }
            // 用字符串形式将上面得到的数组表示出来
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            // #字符出现的次数,一共26对
            String key = sb.toString();
            // 用这个每个字符出现的次数作为键,空列表作为值.当不存在时,也就是,新的字符串时,添加进map,值为空列表
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            // 对键对应的值(列表)添加元素,此时键相同,直接添加对应元素进入,
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}
